package heap;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 *
 *  双指针依次合并    分治合并两两合并
 *  除分治的方式外 还可以用堆排序的方式合并
 */
public class 合并K个排序链表_23 {

    /**
     * 法一  ：依次合并  两个两个来
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = lists[0];
        for (int i = 1; i < lists.length; i++) {
            cur = merge2Lists(cur, lists[i]);
        }
        return cur;
    }

    /**
     * 法二  ：分治法合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists_devide(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * merge 包裹在 merge2Lists 外部 用于分治划分
     * 这种使用双函数进行分治递归的方式值得学习
     */
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start > end) return null;
        if (start == end) return lists[start];
        final int mid = (start + end) >> 1;
        return merge2Lists(merge(lists, start, mid), merge(lists, mid + 1, end));
    }

    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = new ListNode(), tail = head;
        ListNode cur1 = l1, cur2 = l2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                tail.next = cur1;
                cur1 = cur1.next;
            } else {
                tail.next = cur2;
                cur2 = cur1.next;
            }
            tail = tail.next;
        }
        tail.next = cur1 == null ? cur2 : cur1;
        return head.next;
    }


    public ListNode mergeKLists_heap(ListNode[] lists) {
        MinHeap minHeap = new MinHeap(lists);
        ListNode cur = minHeap.pop();
        ListNode head = cur;
        while(cur != null) {
            ListNode next = minHeap.pop();
            cur.next = next;
            cur = next;
        }
        return head;
    }


    /**
     * 现成的队列 每次放一个头部进去  而不是全扔进去
     */
    public ListNode mergeKLists_priorityQueue(ListNode[] lists) {
        // 先把所有丢进来每个进来都排序是有问题的  会导致多次重排序 还不如上边的直接全扔进去一次堆排

        /*Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for(ListNode node:lists) {
            while(node  != null) {
                queue.offer(node);
            }
        }

        ListNode head = queue.poll();
        if(head == null) return null;
        ListNode cur = head;
        while(! queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        return head;*/
        // k个指针的思路  用队列来实现
        Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        // 所有链表都把队首扔进来
        for(ListNode node:lists) {
            if(node  != null) {
                queue.offer(node);
            }
        }
        // 直接拿第一个会把第二个丢掉 因此第二个往后的节点都没有offer进来
        /*ListNode head = queue.poll();
        if(head == null) return null;*/
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(! queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            // 把cur的下一个节点加到队列中排下序
            if(cur.next != null) {
                queue.offer(cur.next);
            }
        }
        return head.next;
    }

    public static void main(String[] args) {
        int[][] list = new int[][]{{1,4,5},{1,3,4},{2,6}};
        ListNode [] listNodes = new ListNode[list.length];

        for (int i = 0; i < list.length; i++) {
            ListNode head = null, cur = null;
            if(list[i].length == 0) continue;
            int val = list[i][0];
            cur = head = new ListNode(val);
            for (int j = 1; j < list[i].length; j++) {
                cur.next = new ListNode(list[i][j]);
                cur = cur.next;
            }
            listNodes[i] = head;
        }

        合并K个排序链表_23 s = new 合并K个排序链表_23();
        s.mergeKLists_priorityQueue(listNodes);
    }
    /**
     * 考虑本次建堆只需要 一个个push  push完一次循环调整  不用每次调整
     * 可以全塞进来heapify 一次就好
     */
    class MinHeap {
        ListNode[] heapData;
        int heapSize = 0;

        public MinHeap(ListNode[] lists) {

            for(ListNode node:lists) {
                while(node  != null) {
                    heapSize ++;
                    node = node.next;
                }
            }
            heapData = new ListNode[heapSize];
            int cur = 0;
            for(ListNode node:lists) {
                while(node  != null) {
                    heapData[cur] = node;
                    cur++;
                    node = node.next;
                }
            }
            buildHeap();
        }


        public void heapify(int i) {
            int right = (i + 1) << 1;
            int left = right - 1 ;

            int smallest = i;

            if(right < heapSize && heapData[right].val < heapData[smallest].val ) {
                smallest = right;
            }

            if(left < heapSize && heapData[left].val < heapData[smallest].val ) {
                smallest = left;
            }
            if(smallest == i) return;
            swap(i, smallest);
            heapify(smallest);
        }

        private void swap(int i, int smallest) {
            ListNode tmp = heapData[i];
            heapData[i] = heapData[smallest];
            heapData[smallest] = tmp;
        }


        public void buildHeap() {
            for(int i = ((heapSize + 1) >> 1) - 1; i >= 0 ; i -- ){
                heapify(i);
            }
        }


        public ListNode pop() {
            if(heapSize == 0) {
                return null;
            }
            ListNode root = heapData[0];
            // 取heapSize - 1  并把heapSize--
            heapData[0] = heapData[--heapSize];
            heapify(0);
            return root;
        }

        /**
         * heap 扩容  用不上
         */
        private void resize() {
            int oldHeapSize = heapSize;
            heapSize = (int) (heapSize * 1.75);
            ListNode[] newArr = new ListNode[heapSize];
            System.arraycopy(heapData, 0 , newArr, 0, oldHeapSize);
            heapData = newArr;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
